package 力扣算法练习.main1.part1;

import java.util.*;

public class day18 {
    /*
    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
    https://leetcode.cn/problems/permutations-ii/
     */
    //看了题解
    public List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length == 0) return result;
        Deque<Integer> temp = new ArrayDeque<>();//记录一种排序的可能
        boolean[] flag = new boolean[nums.length];//记录已经出现过的数字
        Arrays.sort(nums);
        pfs(nums, nums.length, 0, flag, temp, result);
        return result;
    }

    private void pfs(int[] nums, int length, int steps, boolean[] flag, Deque<Integer> temp, List<List<Integer>> result) {
        if (steps == length) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < length; i++) {
            if (flag[i] || i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]) continue;
            temp.addLast(nums[i]);
            flag[i] = true;
            pfs(nums, length, steps + 1, flag, temp, result);
            temp.removeLast();
            flag[i] = false;
        }
    }

    //官方解
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }


    /*
    给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
    你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
    https://leetcode.cn/problems/rotate-image
     */
    //主要观察旋转前和旋转后的索引变化
    //时间复杂度o(n^2)空间复杂度o(n^2)n指矩阵长度
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return;
        int[][] result = new int[n][n];
        //将元素复制到临时数组中(因为提交时候用的是地址值,所以要改变原来的地址指向的内容)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[i][j] = matrix[i][j];
            }
        }
        for (int i = n - 1, index1 = 0; i >= 0; i--, index1++) {
            for (int j = 0, index2 = 0; j < n; j++, index2++) {
                matrix[j][i] = result[index1][index2];
            }
        }
    }
    //官方解
    public void rotate1(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

}



